МІНІСТЕРСТВО ОСВІТИ І НАУКИ УКРАЇНИ
НАЦІОНАЛЬНИЙ УНІВЕРСИТЕТ “ЛЬВІВСЬКА ПОЛІТЕХНІКА”
В.І.Каркульовський, С.П.Ткаченко, І.І.Чура,
ІЗОМОРФІЗМ ГРАФІВ
І Н С Т Р У К Ц І Я № 5
до лабораторної роботи
з курсу
“Дискретні моделі в САПР”
для базового напрямку 6.0804 “Комп’ютерні науки”
Затверджено:
на засіданні кафедри
“Системи автоматизованого провектування”
Протокол N 4 від 18. 10. 2001 р.
Львів – 2001
Ізоморфізм графів. Інструкція до лабораторної роботи №5 з курсу “Дискретні моделі в САПР” для студентів базового напрямку 6.08.04 “Комп’ютерні науки”. /Укл. В.І.Каркульовський, С.П.Ткаченко, І.І.Чура. -Львів: НУ ЛП, 2001р. -12с.
Укладачі: В.І.Каркульовський, канд.техн.наук, доц.,
С.П.Ткаченко, канд.техн.наук, доц.
І.І.Чура, канд.техн.наук, доц..
Відповідальний за випуск: І.І.Мотика, канд.техн.наук, доц.
Рецензенти: Стех Ю.В. , канд.техн.наук, доц.
Матвійків О.М. , канд.техн.наук, доц.
1. МЕТА РОБОТИ
Метою лабораторної роботи є вивчення і дослідження основних підходів до встановлення ізоморфізму графів.
2. ТЕОРЕТИЧНІ ВІДОМОСТІ
Теорія графів дає простий, доступний і потужній інструмент побудови моделей і рішення задач впорядкування взаємозвязаних обєктів. Нині є багато проблем де необхідно дослідити деякі складні системи з допомогою впорядкування їх елементів. До таких проблем відносяться і задачі ідентифікації в електричних схемах, в авіації, в органічній хімії і т.д. Вирішення таких проблем досягається з допомогою встановлення ізоморфізму графів.
Два графа G=(X,U,P) і G'=(X',U',P') називаються ізоморфними, якщо між їх вершинами, а також між їхніми ребрами можна встановити взаємно однозначне співвідношення X <-> X', U <-> U', що зберігає інцидентність, тобто таке, що для всякої пари (x,y)єX ребра u є U, що з'єднує їх, обов'язково існує пара (x',y') є X' і ребро u' є U', що з'єднує їх, і навпаки. Тут P - предикат, інцидентор графа G. Зауважимо, що відношення ізоморфізму графів рефлексивне, симетричне і транзитивне, тобто представляє собою еквівалентність.
На даний час існує досить детальна класифікація розроблених методів рішення такого типу задач /1/. Розглядаючи комбінаторно-логічну природу вказаної задачі можна всі роботи в цьому напрямку розділити на дві групи:
рішення теоретичної задачі встановлення ізоморфізму простих графів;
розробка наближених методів, які найбільш повно враховують обмеження і специфіку задачі з застосуванням характерних ознак об’єкту дослідження.
До першої групи відносяться алгоритми: повного перебору і почергового “підвішування” графів за вершини.
а) Одним з найпростіших з точки зору програмної реалізації, є алгоритм перевірки ізоморфізму графів повним перебором(можливої перенумерації вершин), але складність цього алгоритму є факторіальною.
б) Почергове “підвішування” графів за вершини (всі ребра зрівноважені).
Суть цього алгоритму полягає в знаходженні однакових “підвішаних” графів (за довільні вершини), ізоморфність яких визначаємо. При чому в одному з графів почергово змінюється вершина за яку він “підвішується”. Ізоморфізм графів визначається по їх матрицях суміжності, які формуються по однотипних правилах:
індекс в матриці вершини за яку закріплений (“підвішаний”) граф рівний одиниці;
кортеж вершин в матриці визначається рівнями сусідів;
кортеж вершин в межах кожного рівня сусідів визначається степінню вершини, а також кількістю ребер над нею і нижче її.
Для графа G( рис.1) представлені різні варіанти його “підвіски” рис.2
Рис. 1
Рис.2.
Роботи першої групи рідко використовуються для розробки безпосередньо алгоритмів рішення задачі ідентифікації, але вони дозволяють дати оцінку обчислювальної складності алгоритмів її рішення, які відносяться до задач зі складним рішенням (NP - повні задачі), складність алгоритмів яких є експоненціальною і в деяких випадках сягає О(N!), (N - кількість вершин), тому доводиться відмовлятись від спроб досягнути точними методами їх рішення.
Наближені алгоритми використовують або допустимі рішення точних методів, або побудованні на...
